/**
 *给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
 *
 * 假设二叉树中至少有一个节点。
 *
 *https://leetcode.cn/problems/LwUNpT/
 * 思路：我们可以对其先序或中序遍历，可以确定，无论是先序还是中序遍历，当层数取最大时的访问的第一个节点一定是最底层（高度最高） 最左边（同层从左往右第一个访问） 节点。
 * 在遍历同时，用h记录当前节点从上往下方向的高度，height记录当前全局最高层数，当height发生改变时，用max记录对应节点，当遍历结束即为所求，
 *
 */
class FindBottomLeftValueDfs {
    public int findBottomLeftValue(TreeNode root) {
        dfs(root,1);
        return max.val;
    }
    int H=0;
    TreeNode max=null;
    public void dfs(TreeNode root,int h){
        if(root==null){
            return ;
        }
        if(h>H){
            H=h;
            max=root;
        }
        dfs(root.left,h+1);
        dfs(root.right,h+1);
    }
}